Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
Free, publicly-accessible full text available March 7, 2026
-
Abstract A coupling of random walkers on the same finite graph, who take turns sequentially, is said to be anavoidance couplingif the walkers never collide. Previous studies of these processes have focused almost exclusively on complete graphs, in particular how many walkers an avoidance coupling can include. For other graphs, apart from special cases, it has been unsettled whether even two noncolliding simple random walkers can be coupled. In this article, we construct such a coupling on (i) anyd‐regular graph avoiding a fixed subgraph depending ond; and (ii) any square‐free graph with minimum degree at least three. A corollary of the first result is that a uniformly random regular graph onnvertices admits an avoidance coupling with high probability.more » « less
An official website of the United States government
